The present invention relates to electronic circuits and to digital communication. More particularly, the present invention relates to a bit-table calendar for translating digital communications between a time-division multiplexed (TDM) domain and a cell-based asynchronous transfer mode (ATM) domain.
The present invention has a number of applications in advanced telecommunication systems and networks. One envisioned application of the invention is for use in state-of-the-art telephone central office (CO) switching systems to connect local T1 TDM lines in one area to T1 TDM lines in different area through a high performance ATM backbone. Another application would be at the site of an institutional customer such as a company or research or educational institution for connecting a T1 line provided by a public telephone network to a local ATM network.
This discussion presupposes some familiarity with ATM cell-based switch methodology, such as that described in detail in co-assigned U.S. patent application Ser. No. 08/235,006, filed Apr. 28, 1994, now U.S. Pat. No. 5,583,861, entitled ATM ARCHITECTURE AND SWITCHING ELEMENT, which is hereby incorporated by reference. The present discussion also presumes some familiarity with commonly TDM technology such as that employed in widely available T1 lines used and leased by public telephone companies throughout the United States and E1 lines used in other countries.
Explanation of both the prior art and the invention will be better understood with reference to specific examples, however this should not be taken to limit the invention to the particular examples described. The invention is generalizable to other similar types of communication interfaces and the invention should therefore not be limited except as provided in the attached claims.
T1 type TDM service is a widely used, medium speed digital communication service provided by, among others, public telephone companies in the United States. E1 service is a similar service provided in Europe. A T1/E1 line is conceived of as a single point to point serial digital communication line operating at an overall data speed of 1.544 Mb/s for T1 and 2.098 Mb/s for E1. Serial data on a T1 or E1 line is divided into 125 microsecond intervals, called frames, and each frame is further divided into TDM time slots. T1 lines have 24 slots per frame, and E1 lines have 32 slots per frame. Each T1/E1 slot has a speed of 64 Kb/s: {fraction (1/24)}th of the overall T1 speed or {fraction (1/32)}nd of the overall E1 speed. Each T1/E1 slot can carry an independent serial digital data signal, for example a digitally encoded telephone call. Therefore a single T1 line can carry 24 concurrent telephone calls. Data is routed to a particular telephone call used on which slot it is located. The format of data on a T1 line is shown in diagram 2 of FIG. 1.
Public telephone companies typically sell the capacity on a T1 line on a slot by slot basis, and a user wishing high speed data communication can buy any number of slots. Slots can be aggregated into higher speed channels with the effective channel speed being the combined speed for the number of slots. A standard T1 line can have as many as 24 channels, each having a data rate of 64 Kb/s, or as few as one channel with a data speed of 1.544 Mb/s. A T1 line that is divided into more than one channel is sometimes referred to as xe2x80x9cstructured linexe2x80x9d and a T1 line that carries only one channel is referred to as an xe2x80x9cunstructured line.xe2x80x9d For example, a company having a main office in San Francisco and a satellite office in Palo Alto, might for example, lease eight T1 slots between the two offices and use four of the slots for four separate voice channels and aggregate the four other slots into a single higher speed data channel. The company would therefore have five channels, four at 64 Kb/s for voice, and one at 0.25 Mb/s for data.
In some areas, phone companies have begun to install a new switching architecture into their central offices for use in CO to CO communication. This technology is referred to as cell-based ATM (Asynchronous Transfer Mode) switching. Cell-based ATM switching is designed to effectively serve the needs of both continuous low-bandwidth digital voice data and bursty high-bandwidth data. At the heart of cell-based switching is the cell, a small unit of data with an address identifying its destination and path through the ATM network. The standardized ATM network protocol employs an cell of 53 bytes, 48 bytes of data and 5 bytes of ATM header. The destination of data on an ATM line is determined by the cell header and not by the slot location within a frame as in TDM. Therefore ATM is said to be asynchronous. ATM data transfer speeds are typically much higher than the speed of a T1 line. A typical ATM line operates at 155 Mb/s, or about 100 times faster than a T1 line.
As telephone and digital system carriers have begun adopting cell-based switching for some parts of communication networks, a need has arisen for connecting existing TDM lines into new cell-based ATM switches. This need has been filled by a device referred to in the art as an SAR Processor (SAR stands for Segmentation and Reassembly). An SAR processor provides an interface between a number of TDM lines and a cell-based ATM switch network. The SAR processor typically accomplishes this by collecting data received on a TDM channel in groups of 47 data bytes, and then putting that data into an ATM cell (which has 48 data bytes) for transmission over an ATM switch. The SAR adds one byte of its own header information to each cell, and in some applications adds an additional one byte of data every eight cells for timing purposes. An ATM cell leaving the SAR therefore contains 47 bytes of TDM data for most cells, with possibly every 8th cell for structured lines containing only 46 bytes.
FIG. 1 illustrates some of these concepts in a block diagram showing a central office 5 having an SAR 10, connected to an ATM network 20. As shown in FIG. 1, SAR 10 connects to eight T1 or E1 TDM lines 25 at its TDM interface and to one ATM interface line 15 at its ATM interface. Line 15 is one input into ATM network 20, which may be partly located in CO 5. In the embodiment shown, when these eight interface lines are E1 lines, they can define as many as 256 independent TDM channels, with up to 32 channels per line, or they can define as few as eight high speed channels, with each TDM line carrying one channel. When lines 25 are T1 lines, they can contain up to 192 channels. The format of data on one T1 line is shown in diagram 2.
A basic function of SAR 10 is the temporary storing of data received on lines 25 and the scheduling of data out of the ATM interface line 15. Data is transmitted on line 15 in fixed-width ATM cells at a fixed high speed, and the data rate on the ATM line is typically about 100 times faster that the data rate on any one T1/E1 line. The amount of time it takes to transmit one ATM cell on line 15 is referred to as the ATM cell-time. Data is transmitted on lines 25 on a variable number of channels at various speeds depending on the number of slots allocated to a channel. SAR 10 must buffer this incoming data on various channels until enough data is collected to make an ATM cell (47 bytes) and then must transmit that cell on ATM line 15. SAR 10 must allocate the data space on line 15 fairly among all the TDM channels to insure that delay is kept to a minimum on each channel.
Deciding from which of the 256 possible TDM channels to send a cell during each ATM cell-time is non-trivial. One of the factors that makes the decision complex is that different types of data carried on different channels may be either very sensitive or very insensitive to different types of delay. One kind of delay of concern is the actual cell delay through an SAR, i.e., how much delay is there between an input bit and the subsequent output of that bit. This delay is referred to as latency. A second and often more important type of delay is jitter, or CDV (Cell Delay Variation). This delay refers to the amount of variation in delay that different cells on one channel experience as they are being transmitted through the communications network. Digitized voice data, for example, is very sensitive to CDV. In many common types of voice systems, serial bits must be received at the voice device at the expected speed with no gaps due to CDV. Gaps would cause static or popping which would be intolerable in voice communication. TDM voice data is therefore particularly sensitive to any CDV that results in a slot of voice data not being delivered immediately after the preceding slot. Computer data traffic, on the other hand, is often insensitive to CDV. It, however, can use a lot of bandwidth for short periods of time and so can cause delay in other channels if network resources are not managed well.
A number of methods for scheduling cells from particular channels in a device like SAR 10 have been implemented or discussed in the art. One method for scheduling cells from the TDM lines is the FIFO (First In/First Out) method. According to this method, as soon as a cell from a particular channel is full, it is put in line to be transmitted and is then transmitted through the ATM switch. In a FIFO system, the SAR generally must poll each channel in some particular order to determine when a channel has collected enough data to complete a cell. The FIFO method has the advantage that it is simple to implement. The switch element described in the above referenced co-assigned patent application uses a FIFO queuing technique with proportional bandwidth queues. When that switch element receives a cell of data, it assigns it a certain priority. The switch determines which priority will be served next according to its proportional bandwidth queuing table and then selects the next cell to play according to the FIFO for that priority. One problem with FIFO queuing is that it tends to aggregate all the data flowing through the switch and it therefore cannot finely control the transmission behavior on a particular channel.
Another method for scheduling cells is the use of a calendar circuit. In a calendar circuit, channels are scheduled on a calendar in advance of when they are to be sent. Calendars have the advantage that it is possible to schedule cells from particular channels to achieve many goals, such as minimizing delay on some channels or ensuring fairness between high bandwidth channels by scheduling the cells rather than simply sending a cell that from a channel has a full cell first.
A calendar circuit maintains a table listing each of the active channels. The calendar is responsible for indicating when cells from each of those channels should be sent. The traditional calendar treats the channels independently and schedules in the calendar table when the next cell will be transmitted from that channel. When a new channel is activated, its channel number is placed into the calendar at the next empty time slot. When the playout time reaches that entry, the next cell for that channel is sent and if there is further data from that channel, another cell from that channel is scheduled into the calendar, based on a calculation of the interval between the current time and the future time when the cell can be played out.
Traditional calendar queues are quite large and cumbersome entities because they are generally implemented as linked lists. An example of a linked list is shown in FIG. 2. In a linked list implementation, the calendar maintains a table 90 indexed by frame number 92. Each entry 93 in the table contains an identifier 94 of a channel and a bit 95 indicating whether said channel is the end or tail of the list for that frame number. When the calendar circuit is ready to send out channels at that frame number, the calendar must first look up the entry in link list 90 at that frame number, and then send out a cell for the channel listed in that entry. If the bit 95 at that frame number indicates that the channel is not at the tail of the list, the calendar must then look up in a second list 96 indexed by channel identifier 97 to determine the next channel in the linked list. In this second list, each entry contains a channel identifier 98 for a next channel in the list and a bit 99 indicating whether that channel is the tail channel. The calendar then sends a cell from the channel indicated in that second list, and if that channel is not the tail of the list, the calendar then looks in the entry for that channel to find the next channel in the linked list. In this way, the calendar must traverse the list link by link for each frame until a tail is reached. An example of this is shown as path 91 in the figure.
A linked list implementation of a calendar requires a large amount of complex circuitry to handle the various linked list lookups. This circuitry is difficult to design and debug and uses a significant amount of space on a VLSI circuit. Linked lists also require more time to accomplish the lookups in the list as well as updates to the list because adding and deleting entries in a link list requires traversing the entire link list to reach the tail. Other implementations of linked lists designed to eliminate this problem implement yet another table to indicate the tail of each linked list, but this other table requires still more circuitry and still more processing to update each time the linked list is modified.
What is needed is a type of calendar circuit maintaining the advantages of linked list tables but without the complex and expensive calculations and circuitry that the traditional link list implementation require.
The present invention implements a calendar circuit without the use of linked lists and instead maintains a table of bits that are set to schedule data transmissions from a channel. In a particular embodiment, the present invention has a series of bit tables, one for each T1/E1 line, the tables having a bit location for each possible channel at each of a set number of future frame. In this way, the present invention achieves a superior calendar circuit having a very small and efficient implementation.